package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月8日
*时间：下午5:19:29
*/
public class Q510 {
    /**
     * @param matrix a boolean 2D matrix
     * @return an integer
     */
    public int maximalRectangle(boolean[][] matrix) {
        if (matrix == null || matrix.length <= 0 || matrix[0] == null || matrix[0].length <= 0) {
            return 0;
        }
        int max = 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int dp[][] = new int[n][m];
        int dp1[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j]) {
                    if (j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i][j - 1] + 1;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j]) {
                    if (i == 0) {
                        dp1[i][j] = dp[i][j];
                    } else {
                        dp1[i][j] = cal(i, j, dp);
                    }
                    if (max < dp1[i][j]) {
                        max = dp1[i][j];
                    }
                } else {
                    dp1[i][j] = 0;
                }
            }
        }
        return max;
    }

    private int cal(int i, int j, int[][] dp) {
        int count = 1;
        int maxArea = 0;
        int min = Integer.MAX_VALUE;
        for (; i >= 0; i--) {
            if (dp[i][j] < min) {
                min = dp[i][j];
            }
            if (min == 0) {
                break;
            }
            int area = count * min;
            if (area > maxArea) {
                maxArea = area;
            }
            count++;
        }
        return maxArea;
    }

    @Test
    public void testA() {
        boolean[][] matrix = { { true, true, false, false, true }, { false, true, false, false, true }, { false, false, true, true, true },
                { false, false, true, true, true }, { false, false, false, false, true } };
        System.out.println(maximalRectangle(matrix));
    }
}
